package puzzle.projecteuler.p200;

import java.util.HashSet;
import java.util.List;
import java.util.Set;

import astudy.util.AdvMath.Factors;

public class Problem141C {

	/**
	 * t^2 = qd + r
	 * 这里q,d的位置是对称的，只要r < max(q,d)就可以了
	 * 并不妨假设d^2 = qr
	 * 我们只要求出满足如下条件的n=m^2:
	 * 1) t^2 = qd + r
	 * 2) d^2 = qr
	 * 3) r < max(q,d)
	 * 4) t < 10^6
	 * 
	 * 2),3) => q>d, q>r, 再结合1),知道 d<t<10^6
	 * 
	 * 基本算法如下：
	 * for d in 2..10^6
	 * 	for q|d^2, q>d
	 * 		x = d*q + r
	 * 		if x is square, add x in to set.
	 * 	end
	 * end
	 * @param args
	 */
	public static void main(String[] args) {
		
		long s = System.currentTimeMillis();
		int m = 1000000;
		Set<Long> xs = new HashSet<Long>();
		Factors[] tmp = Factors.factor(m);
		for (int d = 2; d < tmp.length; d ++) {
			List<Factors> qs = tmp[d].merge(tmp[d]).getAllFactors();
			for (Factors q: qs) {
				if (q.longValue() <= d) {
					continue;
				} else {
					long r = (long)d*d/q.longValue();
					long x = (long)d*q.longValue()+r;
					long t = (long)Math.sqrt(x);
					if (t*t == x && t < m) {
						xs.add(x);
						System.out.println(t + "^2=" + q + "*" + d + "+" + r);
					}
				}
			}
		}
		
		long sum = 0;
		for (Long x: xs) {
			sum += x;
		}
		System.out.println("count = " + xs.size());
		System.out.println("sum = " + sum);
		System.out.println((System.currentTimeMillis()-s) + " ms");
	}
}
